import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 力扣38. 外观数列
class Solution {
    public String countAndSay(int n) {
        // 初始值，第一个序列是"1"
        String res = "1";

        // 从2开始生成直到第n个序列
        for (int i = 2; i <= n; i++) {
            // 将当前序列转为字符数组处理
            char[] ch = res.toCharArray();
            StringBuilder temp = new StringBuilder();

            // 记录当前字符和出现次数
            char current = ch[0];
            int count = 1;

            // 遍历字符数组，统计连续相同字符的个数
            for (int j = 1; j < ch.length; j++) {
                if (ch[j] == current) {
                    // 相同字符，计数加1
                    count++;
                } else {
                    // 不同字符，拼接计数和字符
                    temp.append(count).append(current);
                    // 更新当前字符和计数
                    current = ch[j];
                    count = 1;
                }
            }

            // 处理最后一组字符
            temp.append(count).append(current);
            // 更新结果为当前生成的序列
            res = temp.toString();
        }

        return res;
    }
}






// 力扣40. 组合总和 II
class Solution1 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        // 排序是去重的关键
        Arrays.sort(candidates);
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> temp,
                           int[] candidates, int remain, int start) {
        // 终止条件：找到符合条件的组合
        if (remain == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }

        // 遍历候选元素
        for (int i = start; i < candidates.length; i++) {
            // 剪枝：如果当前元素大于剩余目标值，后续元素更大，无需考虑
            if (candidates[i] > remain) {
                break;
            }

            // 去重：跳过相同元素，确保不出现重复组合
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }

            // 选择当前元素
            temp.add(candidates[i]);

            // 递归探索，注意索引+1，确保每个元素只使用一次
            backtrack(result, temp, candidates, remain - candidates[i], i + 1);

            // 回溯：移除最后添加的元素
            temp.remove(temp.size() - 1);
        }
    }
}

